package io.zhengsh.vvip.leetcode.search;

public class Q200_Number_Of_Islands {

    class Solution {
        public int numIslands(char[][] grid) {
            int islandNum = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == '1') {
                        infect(grid, i, j);
                        islandNum++;
                    }
                }
            }
            return islandNum;
        }

        public void infect(char[][] grid, int i, int j) {
            if (i >= grid.length || j >= grid[0].length || i < 0 || j < 0) {
                return;
            }
            if (grid[i][j] == '0' || grid[i][j] == '2') {
                return;
            }

            grid[i][j] = '2';
            infect(grid, i + 1, j);
            infect(grid, i - 1, j);
            infect(grid, i, j + 1);
            infect(grid, i, j - 1);

        }
    }
}
